#include<vector>
#include<utility>
using std::pair;
using std::vector;



class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        if (temperatures.size() < 2) return {0};
        int n = temperatures.size();
        vector<int> ans(n, 0);
        vector<pair<int, int>> stk = {{n-1, temperatures[n-1]}};
        for (int i = n-2; i >= 0; i--) {
            int v = temperatures[i];
            int firstHigherIdx = n;
            while (!stk.empty() && v >= stk.back().second) stk.pop_back();
            if (!stk.empty()) firstHigherIdx = stk.back().first;
            stk.push_back({i, v});
            ans[i] = (firstHigherIdx == n) ? 0 : firstHigherIdx - i;
        }
        return ans;
    }
};